package com.pocket.demo.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 最长连续序列
 *      https://leetcode.cn/problems/longest-consecutive-sequence/?envType=study-plan-v2&envId=top-100-liked
 * @author zhaozhile
 */
public class _123_Array_LongestConsecutive {

    public static int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0){
            return 0;
        }

        Map<Integer, Integer> countNumMap = new HashMap<>();
        for (int num : nums) {
            countNumMap.put(num, 1);
        }

        for (int num : nums) {
            forward(countNumMap, num);
        }

        return maxCount(countNumMap);
    }

    public static int forward(Map<Integer, Integer> countNumMap, int num){
        if (!countNumMap.containsKey(num)){
            return 0;
        }
        int cnt = countNumMap.get(num);
        if (cnt > 1){
            return cnt;
        }

        cnt = forward(countNumMap, num + 1) + 1;
        countNumMap.put(num, cnt);
        return cnt;
    }

    public static int maxCount(Map<Integer, Integer> countNumMap){
        int max = 0;
        for (int num : countNumMap.keySet()){
            max = Math.max(max, countNumMap.get(num));
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(longestConsecutive(new int[]{100,4,200,1,3,2}));
        System.out.println(longestConsecutive(new int[]{0,3,7,2,5,8,4,6,0,1}));
    }

}
